# 【练习】快速排序
# 编写一个Python程序，实现快速排序。
def quicksort(l1):
    if len(l1) <= 1:
        return l1

    median = l1[int(len(l1)/2)]
    list_left = []
    list_right = []
    list_middle = []

    for i in l1:
        if i < median:
            list_left.append(i)
        elif i == median:
            list_middle.append(i)
        else:
            list_right.append(i)

    return quicksort(list_left) + list_middle + quicksort(list_right)

if __name__ == "__main__":
    print(quicksort([1, 2, 3, 4, 6, 5, 4, 1, 2, 6, 9, 7]))


